﻿#define _CRT_SECURE_NO_WARNINGS 


int search(int* nums, int numsSize, int target)
{
	// 初始化 left 与 right 指针 
	int left = 0, right = numsSize - 1;
	// 由于两个指针相交时，当前元素还未判断，因此需要取等号 
	while (left <= right)
	{
		// 先找到区间的中间元素 
		int mid = left + (right - left) / 2;
		// 分三种情况讨论 
		if (nums[mid] == target) return mid;
		else if (nums[mid] > target) right = mid - 1;
		else left = mid + 1;
	}
	// 如果程序⾛到这⾥，说明没有找到⽬标值，返回 -1 
	return -1;
}


class Solution {
public:
	int search(vector<int>& nums, int target) {
		int left = 0, right = nums.size() - 1;
		while (left <= right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] < target) left = mid + 1;
			else if (nums[mid] > target) right = mid - 1;
			else return mid;
		}
		return -1;
	}
};


///////////////////////////////////////////////////
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 处理边界情况
        if (nums.size() == 0)
            return { -1, -1 };

        int begin = 0;
        // 1. ⼆分左端点
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        // 判断是否有结果
        if (nums[left] != target)
            return { -1, -1 };
        else
            begin = left; // 标记⼀下左端点
        // 2. ⼆分右端点
        left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        return { begin, right };
    }
};